COMMENT ⊗   VALID 00003 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002						Starkey paper  S-078
C00007 00003					Shapiro and Smith paper   S-109
C00013 ENDMK
C⊗;
					Starkey paper  S-078
	Reviewer's comments

Since the technique, here defined as the X-0-0 Heuristic, appears to be new to
the author (who would have heard of it from others at Washington State, if it
were generally known) I must conclude that it might be worth while to accept
Starkey's contribution as a short paper.  He should, however, be asked to make a
better search of the literature than he has apparently done, and he should be
more specific in relating this technique to other available techniques, and in
particular he should point out the pitfalls in its use.

This technique, because of the famous Go proverb, is well known to all Go
players and I had assumed that it would be used by all workers who were
programming Go.  I know that Ryder (not referenced by Starkey) considered it
and, if I am not mistaken, used it in his Go program.  Unfortunately Ryder's
Thesis was never published in a technical journal and so did not gain wide
attention.

The technique is, of course, of principal use in games having large branching
factors. Go is one of the best examples.  I would be surprised if the technique
is not being used in many of the better Chess programs, although I am not
currently up to date in this field. The heuristic is of little interest in
checkers because of the small branching factor and because jumps are compulsory,
still further limiting the branching for those situations where the heuristic
might be expected to apply.  Reduced to its essentials, the technique is a way
to limit the amount of effort that is expended on ineffectual branches of the
search tree for those situations where the opponent has a dominating reply which
he could make after most of the players possible plays.

As a rather minor point, I might quarrel with the author's implication that the
X-O-O heuristic is on a par with the Alpha-Beta heuristic, and that it leads to
exactly the same results that would be found by a much longer mini-maxing
analysis made without it.  The X-O-O heuristic simply points to a play that will
deny the opponent an opportunity to exploit a given temporary situation.  For
the Go example shown, the better play might be to allow the two stones in
question to escape, thus tempting the opponent to try to save them, but to so
hem them in that the opponent would have to spend a disproportionate amount
effort in this endeavor.  Alternatively, there could well be a sente play
elsewhere on the board that is more valuable.  Of course, if a temporary
opportunity leads to a win, as in the Chess example, then the heuristic may
point to the only satisfactory play.
				Shapiro and Smith paper   S-109

	Reviewer's comments

Shapiro and Smith have made a first start at progamming Scrabble.  I believe
that they should be encouraged to continue with their research, and to address
themselves to the basic problems that they have so far failed to solve.  The
paper in its present form is marginal in interest and probably should not be
accepted unless there is a shortage of papers of this type.

The main problem that one must face in programming any word game is the large
size of the necessary word list.  A typical collegiate dictionary contains the
order of 130,000 entries, which, with plurals, different verb endings,etc.,
result in well over twice this number of words.  Obviously, many of these words
are too long to be of value in Scrabble while others are relatively unknown but
one would certainly want to store at least 100,000 words.  Such a list is bulky
to store and awkward to search.

The usual trie retrieval scheme is relatively fast but somewhat wasteful of
space.  The storage structure used by the authors is more wasteful than usual in
that it does not identify the found words implicitly but instead simply points
to the fields where the words are stored and no attempt is made to minimize to
space requirements for the storage of these words.  One wonders if the resulting
size of the store may actually slow down the retrieval by more than the amount
saved by the Scrabble-specific nature of the scheme.  Storing the data structure
on disk solves the physical storage problem but greatly slows the retrieval.
The authors quite fail to mention this problem or to give any indication as to
their use of any special techniques to speed retrieval of data from the disk.

The author's canonical ordering of letters, with the high-valued letters and the
less frequently used letters first, has an ordering advantage for Scrabble but
it does result in an unusually slow retrieval rate.  For fast retrieval one
would want the most plentiful letters first.  Again, one wonders if it would not
be better to reverse the retrieval order, retrieving all possible words, and
only then to consider them in reverse order.

Finally, the authors have left undone many essential features of the game, as
indeed they themselves point out in the concluding section of the paper.  Until
these features are properly addressed, the paper cannot be considered complete
enough to warrent publication.